package org.labuladong.滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-1:01
 * @Description:
 * @version: 1.0
 */
public class LC438_找到字符串中所有字母异位词 {
		public List<Integer> findAnagrams(String s, String t) {
			Map<Character, Integer> need = new HashMap<>();
			Map<Character, Integer> window = new HashMap<>();

			// 统计t中每个字符的出现次数
			for (char c : t.toCharArray()) {
				need.put(c, need.getOrDefault(c, 0) + 1);
			}

			int left = 0, right = 0;
			int valid = 0; // 记录窗口中满足条件的字符数量
			List<Integer> res = new ArrayList<>(); // 记录结果

			while (right < s.length()) {
				char c = s.charAt(right);
				right++;

				// 如果c是t中的字符，则更新窗口计数
				if (need.containsKey(c)) {
					window.put(c, window.getOrDefault(c, 0) + 1);
					if (window.get(c).equals(need.get(c))) {
						valid++;
					}
				}

				// 当窗口大小等于t的长度时，开始判断并可能收缩窗口
				while (right - left >= t.length()) {
					// 如果当前窗口是有效的，记录起始索引
					if (valid == need.size()) {
						// 当窗口符合条件时，把起始索引加入 res
						res.add(left);
					}

					char d = s.charAt(left);
					left++;

					// 如果d是t中的字符，则更新窗口计数
					if (need.containsKey(d)) {
						if (window.get(d).equals(need.get(d))) {
							valid--;
						}
						window.put(d, window.get(d) - 1);
					}
				}
			}

			return res;
		}

		public static void main(String[] args) {
			LC438_找到字符串中所有字母异位词 solution = new LC438_找到字符串中所有字母异位词();
			String s = "cbaebabacd";
			String t = "abc";
			System.out.println("Starting indices of anagram substrings: " + solution.findAnagrams(s, t)); // Expected output: [0, 6]
		}
	}